package com.atguigu.dynamic;

/**
 * @author tbwtbw
 * @create 2021-11-24 19:40
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w = {1, 4, 3};//物品的重量
        int[] val = {1500, 3000, 2000}; //物品的价值 这里val[i] 就是前面讲的v[i]
        int m = 4; //背包的容量
        int n = val.length; //物品的个数

        int[][] v = new int[n + 1][m + 1];//加1是要留出空的一行一列，否则放第一个物品时会越界
        int[][] path = new int[n + 1][m + 1];//记录放入的路径

        for (int i = 1; i < v.length; i++) {//不遍历第一行第一列
            for (int j = 1; j < v[0].length; j++) {//j 是当前背包的容量
                if (w[i - 1] > j) {//物品是从0开始
                    v[i][j] = v[i - 1][j];//放不进去，沿用上面的方案，也就是只放前面 i-1 个物品的方案
                } else {//能放进去
                    if (v[i - 1][j] > (val[i - 1] + v[i - 1][j - w[i - 1]])) {//不放i比放i更好
                        v[i][j] = v[i - 1][j];
                    } else {
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        path[i][j] = 1;//在这个地方标记为1，因为在这里才是真正的新加入了一个物品！
                    }
                }
            }
        }

        for (int[] ints : v) {
            for (int j = 0; j < v[0].length; j++) {
                System.out.print(ints[j] + "\t");
            }
            System.out.println();
        }
        System.out.println("============================");

//        输出最后我们是放入的哪些商品
//        遍历path, 这样输出会把所有的放入情况都得到, 其实我们只需要最后的放入
//		for(int i = 0; i < path.length; i++) {
//			for(int j=0; j < path[i].length; j++) {
//				if(path[i][j] == 1) {
//					System.out.printf("第%d个商品放入到背包\n", i);
//				}
//			}
//		}


        //动脑筋
        int i = path.length - 1; //行的最大下标
        int j = path[0].length - 1;  //列的最大下标
        while (i > 0 && j > 0) { //从path的最后开始找
            if (path[i][j] == 1) {
                System.out.printf("第%d个商品放入到背包\n", i);
                j -= w[i - 1]; //w[i-1]。j为什么要减掉当前物品的容量呢，因为要把这个物品从包里拿出去，再看看剩下的物品是什么！
            }
            i--;//表示减少物品，已经访问完了，如果放了i进去，就会在上面输出，没放就不管了
        }
    }
}